jupytext:
  formats: md:myst
  text_representation:
    extension: .md
    format_name: myst
    format_version: 0.13
    jupytext_version: 1.11.5
kernelspec:
  display_name: Python 3
  language: python
  name: python3

Number Theory

We begin our systematic study of the set of integers Z\Bbb{Z}, and its properties. This is the part of mathematics called number theory and we will give an introduction to this field of mathematics

One important property of integers is that they are ordered. We can talk about one integer being greater than another integer

bdg-warningRecall Z+=\Set1,2,3,\Bbb{Z}^+=\Set{1,2,3,\cdots}, the set of positive integers

Let k,mZ, We saykm      mkZ+\Set0 Let\ k,m\in\Bbb{Z}\text{, We say}\\ k\le m\ \iff\ m-k\in\mathbb{Z}^+\cup\Set{0}

" \le " has some important properties

  1. If kmk\le m and  mn\ m\le n then knk\le n is called the Transitive Property
  2. If kmk\le m and  mk\ m\le k then m=km=k is called the Anti-Symmetry Property
  3. kkk\le k is called the Reflexive Property

Another way to look at "\le" is geometrically using a number line

import matplotlib.pyplot as plt
import matplotlib.ticker as ticker

# Setup a plot such that only the bottom spine is shown
def setup(ax):
    ax.spines['right'].set_color('none')
    ax.spines['left'].set_color('none')
    ax.spines['top'].set_color('none')
    ax.yaxis.set_major_locator(ticker.NullLocator())
    ax.xaxis.set_ticks_position('bottom')
    ax.tick_params(which='major', width=1.00)
    ax.set_xlim(-5, 5)

plt.figure(figsize=(10, 5))
n = 8

ax = plt.subplot(n, 1, 2)
setup(ax)
ax.xaxis.set_major_locator(ticker.MultipleLocator(1))
ax.set_xlabel("Number Line, ℤ")
ax.text(-5, 1, "$\cdots\ -n\ \ \cdots$", fontsize=14, ha='center', va='center')
ax.text(5, 1, "$\cdots\ n\ \cdots$", fontsize=14, ha='center', va='center')

# Add arrow ends to the x-axis
arrowprops = dict(arrowstyle='<|-|>', linewidth=2.5, color='black')
ax.annotate('', xy=(-4, 1), xytext=(4, 1), arrowprops=arrowprops)

plt.show()

Then kmk\le m iff kk is not to the right of mm,
for example for (k,m)(k,m) being (4,3)(-4,-3) then (43)(-4\le -3)

" \le " is an example of mathematical object called a linear or total order

If we change property Anti-Symmetry and keep the Reflexive and Transitive we get another type of mathematical object called an equivalence relation

Well Ordered Property

Well Ordered Property W.O.P.
: Every non-empty subset SZ\mathrm{S}\subseteq\Bbb{Z} that is bounded below has a least member

# Setup a plot such that only the bottom spine is shown
def setup(ax):
    ax.spines['right'].set_color('none')
    ax.spines['left'].set_color('none')
    ax.spines['top'].set_color('none')
    ax.yaxis.set_major_locator(ticker.NullLocator())
    ax.set_xlim(-5, 5)
    ax.xaxis.set_major_locator(ticker.NullLocator())
    ax.xaxis.set_minor_locator(ticker.NullLocator())

plt.figure(figsize=(10, 5))
n = 8

ax = plt.subplot(n, 1, 2)
setup(ax)
ax.set_xlabel("Number Line, ℤ")

# Add arrow ends to the x-axis
arrowprops = dict(arrowstyle='-|>', linewidth=1, color='black')
ax.annotate('k', xy=(-4, 0), xytext=(-4, 1), arrowprops=arrowprops)
ax.annotate('x - smallest element in $\mathrm{S}$', xy=(-3, 0), xytext=(-3, 2), arrowprops=arrowprops)
ax.text(-1, 0.5, "The Set $\mathrm{S}$", color="white", ha="center", va="center", weight="bold")
plt.fill("j", "k", "0.7",
         data={"j": [-3, -3, 1, 1],
               "k": [0, 1, 1, 0]})
plt.show()

This property is important because it allows us to prove the principle of mathematical induction among other important result

The rational number do not obey the W.O.P. and this in part motivates the construction of the real numbers as the following example shows

Division

The first concept we will deal with is division of integers we examine when baZ, a,bZ\frac{b}{a}\in\Bbb{Z},\ a,b\in\Bbb{Z}

Primes

That there is only one way to factor a composite number as a product of primes is the following result There is only one prime factorization for a composite number

The method of determining primality or primality test is dependent on having a list of prime numbers up to the square root of the number to be tested

We can get this list using the Sieve of Erathosthenes

Suppose we want to find all the prime numbers less than a certain number say 100100

We write a list of the first one hundred numbers. We exclude 11 since it is not a prime. We then circle the number 2, and cross off every second number after, ie cross cross all multiples of 2. We now circle the first uncrossed number which is 3, it is prime. We now cross off every third number, the multiples of 3. We now circle the next uncrossed off number, 5, it is prime, and we cross off all multiples of 5. We now circle the next uncrossed off number, 7 it is a prime, and cross off all multiples of 7.

In view of Theorem 3, every uncrossed off number is prime.

In fact if we have a list up to 120, these 4 iterations of the algorithm will give all primes less then 120, by Theorem 3

While the list of prime numbers will never be complete, the search for the largest known primes number is very active.

For about the last 300 years the largest known prime number has been a special type of number called Mersenne Prime

Remainders

Division Algorithm

Greatest Common Divisor & Least Common Multiple

Let a,bZ+a,b\in\Bbb{Z}^+, ie, a,b1a,b\ge 1

Greatest Common Divisor

The gcd(a,b)gcd(a,b) will exist because there are only a finite number of divisors of aa and bb and the lists for both aa and bb of divisors contain the number 11

badge-warningExample Find the ged(14,21)ged(14,21)

The prime factorization of 14=2714 = 2\cdot 7
The prime factorization of 21=3721 = 3\cdot 7
Clearly ged(14,21)=7ged(14,21)=7

bdg-successDefinitions

  1. If ged(a,b)=1ged(a,b)=1 we say aa and bb are relatively prime
  2. The set of numbers \Seta1,a2,\Set{a_1,a_2,\cdots} are called pairwise relatively prime if ged(ai,bj)=1, ijged(a_i,b_j)=1,\ \forall i\ne j bdg-secondaryeg \Set2,7,15\Set{2,7,15}

The prime factorizations of aa and bb gives us a means to find and write down the gcd(a,b)gcd(a,b)

a &= p_{1}^{n_1}\cdot p_{2}^{n_2}\cdot p_{3}^{n_3}\cdot \cdots p_{t}^{n_t}\cdot\ ,\ n_i\ge 0\\ b &= p_{1}^{m_1}\cdot p_{2}^{m_2}\cdot p_{3}^{m_3}\cdot \cdots p_{t}^{m_t}\cdot\ ,\ m_i\ge 0

Then ged(a,b)=p1k1p2k2ptktged(a, b) = p_{1}^{k_1}\cdot p_{2}^{k_2}\cdot \cdots p_{t}^{k_t}\cdot
where ki=min(ni,mi)k_i=min(n_i,m_i)

This of course assumes that we the prime factorizations of aa and bb
This can be a difficulty when finding the gcd(a,b)gcd(a,b)

Least Common Multiple

The lcm(a,b)lcm(a,b) exists because the set of the set of multiples aa and bb is a non-empty set of integers bounded below. By the Well Ordered Property it has a least element

With the notation above, we can calculate lcm(a,b)lcm(a,b)

lcm(a,b)=P1r1ptrt where ri=max(ni,mi) lcm(a,b) = P_{1}^{r_1} \cdots p_{t}^{r_t}\ where\ r_i=max(n_i, m_i)

To calculate gcd(a,b)gcd(a,b) and hence lcm(a,b)lcm(a,b) by eqth6 we don't have to find the prime factorization of a,ba, b We can use the Euclidean Algorithm, essentially a repeated application of the Division Algorithm to find gcd(a,b)gcd(a,b). This method is also used to find s,ts, t in the following theorem

Modular Arithmetic

Consider the question:
A computer program takes 117 hours to run. It is started at 4pm. What time if day will it be complete?

Since we are only considering the time of day and not the actual day, we must convert 117117 hours into days and hours and add the number if hours to 4pm

bdg-successSolution 117=4(24)+21117 = 4 \cdot (24) + 21 we then add 21 hours to 4pm to get 1pm

What we have done in the above calculation is addition modulo 24\textcolor{Orange}{\textit{addition modulo 24}} since we are only concerned with the 24 hours in a day and not the number of days involved

If aa and bb are integers and mm is a positive integer, then aa is congruent to be bb modulo mm if mm divides aba-b

bdg-InfoNotation ab(modm)a\equiv b\pmod m iff mabm\mid a - b
That is aa, bb have the same remainder when divided by mm

a,b,mZ, m2a,b,m\in\Bbb{Z},\ m\ge 2 then ab(modm)a\equiv b\pmod m iff mabm\mid a - b or a=b+km, kZa=b+km,\ k\in\Bbb{Z}
Or in words aa and bb have the same remainder when divided mm using the division algorithm

The set of all integers congruent to an integer a modulo m is called the congruence class of a modulo m and treat the union of these equivalence classes is the set of integers

[k]_m &=\text{ congruence class of a modulo $m$}\\ &=\Set{a\in\Bbb{Z}\mid a\equiv k\pmod m}\\ &=\Set{a+km\mid k\in\Bbb{Z}}

If we take congruences modulo mm of Z\Bbb{Z} it splits into mm distinct congruent classes

Zm=\Set[0]m,[1]m,,[m1]m\Bbb{Z}_m=\Set{[0]_m,[1]_m,\cdots,[m-1]_m}

bdg-secondaryExample Let m=7m=7

\Bbb{Z}_7=&\Set{[0]_7,[1]_7,[2]_7,\cdots,[6]_7}\\ [2]_7=&\Set{\cdots -19, -12, -5, 2, 9, 16, 23,\cdots}\\

Pseudo Random Numbers

An application of modular arithmetic

Randomly chosen numbers are often needed for computer simulations. Because the numbers used are generated by systematic methods they are not truly random and so are called pseudo-random numbers

A commonly used procedure is called the linear congruential method

Choose four integers: m,a,c,x0m, a, c, x_0

m\ &=\ modulus &2\le\ &a& \lt m\\ a\ &=\ multiplier &0\le\ &c& \lt m\\ c\ &=\ increment\ \ &0\le\ &x_0& \lt m\\ x_0\ &=\ seed\\

We use these numbers to generate a sequence of pseudo-random numbers \setxn\set{x_n} with 0xn<m, n=0,1,2,0\le x_n\lt m, \ \forall n=0,1,2,\cdots , by using the recursive definition

xn+1=axn+c(modm)x_{n+1} = ax_n+c\pmod m

Many computer experiments need pseudo-random numbers between 0 and 1
To get these take xnm\frac{x_n}{m}

Let us consider the following examples

  1. Take m=9, a=7,c=4,x9=3m=9,\ a=7, c=4, x_9 = 3

Then xn+1=7xn+4(mod9)x_{n+1} = 7x_n + 4\pmod 9

x_0 &= 3\\ x_1 &= 7\cdot 3 + 4 &= 25& \equiv 7 \pmod 9\\ x_2 &= 7\cdot 7 + 4 &= 53& \equiv 8 \pmod 9\\ x_3 &= 7\cdot 8 + 4 &= 60& \equiv 6 \pmod 9\\ x_4 &= 7\cdot 6 + 4 &= 46& \equiv 1 \pmod 9\\ x_5 &= 7\cdot 1 + 4 &= 11& \equiv 2 \pmod 9\\ x_6 &= 7\cdot 2 + 4 &= 18& \equiv 0 \pmod 9\\ x_7 &= 7\cdot 0 + 4 &=\ 4& \equiv 4 \pmod 9\\ x_8 &= 7\cdot 4 + 4 &= 32& \equiv 5 \pmod 9\\ x_9 &= 7\cdot 5 + 4 &= 39& \equiv 3 \pmod 9\\

Since x0=x9x_0=x_9, and the next term depends on only the previous term, the sequence repeats after 9 different outputs this generator thus gives the sequence
3,7,8,6,1,2,0,4,5,3,7,8,6,1,2,0,4,5, \mathbf{3, 7, 8, 6, 1, 2, 0, 4, 5, 3, 7, 8, 6, 1, 2, 0, 4, 5,\ \cdots}

The sequence generated need not be of length mm before repetition occurs

Consider m=10m = 10, a=3a = 3 c=1c = 1, x0=1x_0 = 1

Then xn+1=3xn+1(mod1)0x_{n+1}=3x_n+1\pmod 10 and

x_0 &= 1\\ x_1 &= 4\\ x_2 &= 3\cdot 4 + 1 &= 13& \equiv 3 \pmod {10}\\ x_3 &= 3\cdot 3 + 1 &= 10& \equiv 0 \pmod {10}\\ x_4 &= 3\cdot 0 + 1 &= 1\ & = 1\\

Thus we get the sequence
1,4,3,0,1,4,3,0, \mathbf{1, 4, 3, 0, 1, 4, 3, 0,\ \cdots}

However, conditions can be put on m, a, c, x0m,\ a,\ c,\ x_0 so that the resulting sequence has a very long period

For example, a widely used generator, has
m=2311m=2^{31}-1, a=75=16,807,c=0a=7^5=16,807, c=0

This pure-multiplicative generator (called so because c=0c=0) generates a sequence 23112^{31}-1 numbers long before repetition for any seed, x0, 1x0<m1\le x_0 <m

Another Application

Of Modular Arithmetic

Let nZ+n\in\Bbb{Z}^+ Then 3n3\mid n iff 33 divides the sum of the digits of its decimal representation as well, 9n9\mid n iff 99 divides the sum of the digits of its decimal representation

This is so because 101(mod3)10\equiv 1\pmod 3 and 101(mod9)10\equiv 1\pmod 9

Let n=ak10k+ak110k1++a110+a0Let\ n=a_k10^k+a_{k-1}10^{k-1}+\cdots+ a_1\cdot 10 + a_0

Now 3n3\mid n if and only if n0(mod3)n\equiv 0\pmod 3 repeated application of following prf:refmodtheory gives

&n\pmod 3\\ &= (a_k10^k+a_{k-1}10^{k-1}+\cdots+ a_1\cdot 10 + a_0)\pmod 3\\ &= (a_k10^k)\pmod 3+(a_{k-1}10^{k-1})\pmod 3 + \cdots + a_0\pmod 3\\ &= a_k\pmod 3 (10\pmod 3)^k+a_{k-1} (10\pmod 3)^{k-1}\pmod 3 + \cdots + a_0\pmod 3\\ &= a_k\pmod 3 (1)^k+a_{k-1} (1)^{k-1}\pmod 3 + \cdots + a_0\pmod 3\\ &= a_k\pmod 3 +a_{k-1} \pmod 3 + \cdots + a_0\pmod 3\\ &= (a_k +a_{k-1} + \cdots + a_0)\pmod 3\\